package test3.recursion;

import java.util.HashMap;
import java.util.Map;

/**
 * 剑指 Offer 10- II. 青蛙跳台阶问题  斐波拉切数列算法改造
 */
public class NumWays {

    public static void main(String[] args) {
        int i = new NumWays().numWays(7);
        System.out.println(i);
    }

    public int numWays(int n) {
        Map<Integer, Integer> map = new HashMap<>();
        return recursion(n, map);
    }

    private int recursion(int n, Map<Integer, Integer> map) {
        if (n == 0 || n == 1) return 1;
        if (map.containsKey(n)) return map.get(n);
        int nums = (recursion(n - 1, map) + recursion(n - 2, map)) % 1000000007;
        map.put(n, nums);
        return nums;
    }


}
